{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Leaf in a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findClosestLeaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树最近的叶节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>每个结点的值互不相同</strong>&nbsp;的二叉树，和一个目标整数值 <code>k</code>，返回 <em>树中与目标值 <code>k</code>&nbsp; <strong>最近的叶结点</strong></em> 。&nbsp;</p>\n",
    "\n",
    "<p><strong>与叶结点最近</strong><em> </em>表示在二叉树中到达该叶节点需要行进的边数与到达其它叶结点相比最少。而且，当一个结点没有孩子结点时称其为叶结点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/13/closest1-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1, 3, 2], k = 1\n",
    "<strong>输出：</strong> 2\n",
    "<strong>解释：</strong> 2 和 3 都是距离目标 1 最近的叶节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/13/closest2-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1], k = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>最近的叶节点是根结点自身。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/13/closest3-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,null,null,null,5,null,6], k = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>值为 3（而不是值为 6）的叶节点是距离结点 2 的最近结点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树节点数在&nbsp;<code>[1, 1000]</code> 范围内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li>每个节点值都 <strong>不同</strong></li>\n",
    "\t<li>给定的二叉树中有某个结点使得&nbsp;<code>node.val == k</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-leaf-in-a-binary-tree](https://leetcode.cn/problems/closest-leaf-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-leaf-in-a-binary-tree](https://leetcode.cn/problems/closest-leaf-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2]\\n1', '[1]\\n1', '[1,2,3,4,null,null,null,5,null,6]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaf=set()\n",
    "        q=collections.deque()\n",
    "        q.append(root)\n",
    "        #ans=float(\"inf\")\n",
    "        #ret=0\n",
    "        #level=0\n",
    "        e=collections.defaultdict(list)\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            for i in range(n):\n",
    "                tp=q.popleft()\n",
    "                find=False\n",
    "                if tp.left:\n",
    "                    q.append(tp.left)\n",
    "                    e[tp.val].append(tp.left.val)\n",
    "                    e[tp.left.val].append(tp.val)\n",
    "                    find=True\n",
    "                if tp.right:\n",
    "                    q.append(tp.right)\n",
    "                    e[tp.val].append(tp.right.val)\n",
    "                    e[tp.right.val].append(tp.val)\n",
    "                    find=True\n",
    "                if not find :\n",
    "                    leaf.add(tp.val)\n",
    "                #    ret=min(ret,)\n",
    "        #print(e)\n",
    "        #print(leaf)\n",
    "        \n",
    "        q.append((0,k))\n",
    "        find=set()\n",
    "        find.add(k)\n",
    "        while q:\n",
    "            d,node=q.popleft()\n",
    "            #print(d,node)\n",
    "            if node in leaf:\n",
    "                return node\n",
    "            for i in e[node]:\n",
    "                if i not in find:\n",
    "                    find.add(i)\n",
    "                    q.append((d+1,i))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.parents = {}\n",
    "        self.target = None\n",
    "        self.buildParents(root, k, None)\n",
    "\n",
    "        q = [self.target]\n",
    "        visited = set([])\n",
    "\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            visited.add(cur)\n",
    "            if cur.left is None and cur.right is None:\n",
    "                return cur.val\n",
    "            if cur.left and cur.left not in visited: q.append(cur.left)\n",
    "            if cur.right and cur.right not in visited: q.append(cur.right)\n",
    "            pat = self.parents.get(cur, None)\n",
    "            if pat and pat not in visited: q.append(pat)\n",
    "\n",
    "    def buildParents(self, root, k, pat):\n",
    "        if root is None or self.target:\n",
    "            return\n",
    "\n",
    "        self.parents[root] = pat\n",
    "\n",
    "        if root.val == k:\n",
    "            self.target = root\n",
    "\n",
    "        self.buildParents(root.left, k, root)\n",
    "        self.buildParents(root.right, k, root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.parents = {}\n",
    "        target = self.buildParents(root, k, None)\n",
    "\n",
    "        q = [target]\n",
    "        visited = set([])\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                cur = q.pop(0)\n",
    "                visited.add(cur)\n",
    "                if cur.left is None and cur.right is None:\n",
    "                    return cur.val\n",
    "                if cur.left and cur.left not in visited: q.append(cur.left)\n",
    "                if cur.right and cur.right not in visited: q.append(cur.right)\n",
    "                pat = self.parents.get(cur, None)\n",
    "                if pat and pat not in visited: q.append(pat)\n",
    "\n",
    "\n",
    "\n",
    "    def buildParents(self, root, k, pat):\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        self.parents[root] = pat\n",
    "\n",
    "        if root.val == k:\n",
    "            return root\n",
    "\n",
    "        left = self.buildParents(root.left, k, root)\n",
    "        right = self.buildParents(root.right, k, root)\n",
    "\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        p={}\n",
    "        def relation(cur,fa):\n",
    "            nonlocal p\n",
    "            if not cur :\n",
    "                return \n",
    "            p[cur]=fa\n",
    "            relation(cur.left,cur)\n",
    "            relation(cur.right,cur)\n",
    "            return \n",
    "        relation(root,None)\n",
    "     \n",
    "        vis=set()\n",
    "        def check(r):\n",
    "            nonlocal vis\n",
    "            if r in vis:\n",
    "                return float(\"inf\"),None\n",
    "            vis.add(r)\n",
    "            if not r.left and not r.right:\n",
    "                return 1,r.val\n",
    "            if r.left:\n",
    "                lside,lval=check(r.left)\n",
    "            else:\n",
    "                lside,lval=float(\"inf\"),None\n",
    "            if r.right:\n",
    "                rside,rval=check(r.right)\n",
    "            else:\n",
    "                rside,rval=float(\"inf\"),None\n",
    "            if p[r]!=None :\n",
    "                topside,topval=check(p[r])\n",
    "            else:\n",
    "                topside,topval=float(\"inf\"),None\n",
    "            mi=min(topside,rside,lside)\n",
    "            if lside==mi:\n",
    "                return lside+1,lval\n",
    "            elif topside==mi:\n",
    "                return topside+1,topval\n",
    "            elif rside==mi:\n",
    "                return rside+1,rval\n",
    "        ans=0\n",
    "        def find(r):\n",
    "            nonlocal ans \n",
    "            if not r:\n",
    "                return \n",
    "            if r.val ==k:\n",
    "                vis=set()\n",
    "                ans=check(r)\n",
    "                return \n",
    "            find(r.left)\n",
    "            find(r.right)\n",
    "            return \n",
    "        find(root)\n",
    "        return ans[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ret = None\n",
    "        min_d = float(\"inf\")\n",
    "        def dfs(node):\n",
    "            nonlocal ret, min_d\n",
    "            if not node.left and not node.right:\n",
    "                if node.val == k:\n",
    "                    ret = node.val\n",
    "                    min_d = 0\n",
    "                return 1, node.val, node.val == k\n",
    "            left_depth, left_lowest_leaf, left_depth_k = float(\"inf\"), None, -1\n",
    "            right_depth, right_lowest_leaf, right_depth_k = float(\"inf\"), None, -1\n",
    "            if node.left:\n",
    "                left_depth, left_lowest_leaf, left_depth_k = dfs(node.left)\n",
    "            if node.right:\n",
    "                right_depth, right_lowest_leaf, right_depth_k = dfs(node.right)\n",
    "            \n",
    "            if left_depth <= right_depth:\n",
    "                curr_depth = left_depth\n",
    "                curr_leaf = left_lowest_leaf\n",
    "            else:\n",
    "                curr_depth = right_depth\n",
    "                curr_leaf = right_lowest_leaf\n",
    "            curr_depth_k = -1\n",
    "            if node.val == k:\n",
    "                print(node.val, curr_depth, curr_leaf, left_depth, right_depth)\n",
    "                if curr_depth < min_d:\n",
    "                    min_d = curr_depth\n",
    "                    ret = curr_leaf\n",
    "                curr_depth_k = 1\n",
    "            elif left_depth_k >= 1:\n",
    "                if right_depth + left_depth_k < min_d:\n",
    "                    min_d = right_depth + left_depth_k\n",
    "                    ret = right_lowest_leaf\n",
    "                curr_depth_k = left_depth_k + 1\n",
    "            elif right_depth_k >= 1:\n",
    "                if left_depth + right_depth_k < min_d:\n",
    "                    min_d = left_depth + right_depth_k \n",
    "                    ret = left_lowest_leaf\n",
    "                curr_depth_k = right_depth_k + 1\n",
    "            # print(node.val, curr_depth, curr_leaf, curr_depth_k)\n",
    "            return curr_depth + 1, curr_leaf, curr_depth_k\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return ret\n",
    "\n",
    "            \n",
    "                \n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\"\"\"\n",
    "graph = {\n",
    "    1: [2, 3],\n",
    "    2: [1, 4, 5],\n",
    "    3: [1, 6, 7],\n",
    "    4: [2],\n",
    "    5: [2],\n",
    "    6: [3],\n",
    "    7: [3]\n",
    "}\n",
    "\n",
    "leaves = {4, 5, 6, 7}\n",
    "用visited去重，从1开始我们到2，然后到2后，我们可以到1，如果没有visited的话\n",
    "就会1->2, 2->1这样循环\n",
    "\n",
    "因为使用bfs, 一层一层的搜索，最早碰到的就是最近的\n",
    "\n",
    "构建graph, 如果是根节点，放入leaves。\n",
    "如果存在左节点，构建图，然后遍历左子树\n",
    "如果存在右节点，构建图，然后遍历右子树\n",
    "\n",
    "然后把目标值放入queue, 如果找到目标(leaves),就返回node\n",
    "遍历这个node的邻居，如果邻居还没访问过，就放入queue\n",
    "\"\"\"\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaves = set()\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "                leaves.add(root.val)\n",
    "\n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "\n",
    "        build_graph(root)\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if node in leaves:\n",
    "                return node\n",
    "            \n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        leaves = set()\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if not root.left and not root.right:  # 判断叶子节点\n",
    "                leaves.add(root.val)\n",
    "            \n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "        \n",
    "        build_graph(root)\n",
    "\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node in leaves:  # 如果该节点是叶子节点\n",
    "                return node\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    visited.add(neighbor)\n",
    "                    queue.append(neighbor)\n",
    "        return -1  # Should not reach here as there must be a leaf in the tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if root.left == None and root.right == None:\n",
    "            if root.val == k:\n",
    "                return root.val\n",
    "            else:\n",
    "                return -1\n",
    "        self.adjVex = defaultdict(list)\n",
    "        def dfs(node, parent):\n",
    "            if node:\n",
    "                if parent:\n",
    "                    self.adjVex[node].append(parent)\n",
    "                    self.adjVex[parent].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        dfs(root,None)\n",
    "        start = None\n",
    "        for node in self.adjVex:\n",
    "            if node.val == k:\n",
    "                start = node\n",
    "                break\n",
    "        queue = [start]\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            if cur.left == None and cur.right == None:\n",
    "                return  cur.val\n",
    "            for nxt in self.adjVex[cur]:\n",
    "                if nxt not in visited:\n",
    "                    visited.add(nxt)\n",
    "                    queue.append(nxt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        cache = dict()\n",
    "\n",
    "        def search(root): #  -> (TreeNode, int)\n",
    "            if root is None:\n",
    "                return None, -1\n",
    "            leaf_l, dp_l = search(root.left)\n",
    "            leaf_r, dp_r = search(root.right)\n",
    "            # print(leaf_l, dp_l, leaf_r, dp_r)\n",
    "            nearest_leaf, depth = root.val, 0\n",
    "\n",
    "            if (dp_l >=0 and dp_l<=dp_r) or (dp_r <0 and dp_l>=0):\n",
    "                nearest_leaf = leaf_l\n",
    "                depth = dp_l+1\n",
    "            elif (dp_r >=0 and dp_l>dp_r) or (dp_l <0 and dp_r >=0):\n",
    "                nearest_leaf = leaf_r\n",
    "                depth = dp_r+1\n",
    "                \n",
    "            \n",
    "            cache[root.val] = (nearest_leaf, depth)\n",
    "            return nearest_leaf, depth\n",
    "        \n",
    "        search(root)\n",
    "        print(cache)\n",
    "\n",
    "        def update(root, new_leaf, new_dp):\n",
    "            if root is None:\n",
    "                return None\n",
    "            \n",
    "            root_val = root.val\n",
    "            nearest_leaf, depth = cache[root_val]\n",
    "            if new_dp < depth:\n",
    "                nearest_leaf = new_leaf\n",
    "                depth = new_dp\n",
    "                cache[root_val] =(nearest_leaf, depth)\n",
    "            \n",
    "            if root.val == k:\n",
    "                return nearest_leaf\n",
    "\n",
    "            res_l = update(root.left, nearest_leaf, depth+1)\n",
    "            if res_l:\n",
    "                return res_l\n",
    "            res_r = update(root.right, nearest_leaf, depth+1)\n",
    "            if res_r:\n",
    "                return res_r\n",
    "        \n",
    "        leaf, root_dp = cache[root.val]\n",
    "        return update(root, leaf, root_dp)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaves = set()\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "                leaves.add(root.val)\n",
    "            \n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "        \n",
    "        build_graph(root)\n",
    "\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if node in leaves:\n",
    "                return node\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        leaves = set()\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if not root.left and not root.right:  # 判断叶子节点\n",
    "                leaves.add(root.val)\n",
    "            \n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "        \n",
    "        build_graph(root)\n",
    "\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node in leaves:  # 如果该节点是叶子节点\n",
    "                return node\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    visited.add(neighbor)\n",
    "                    queue.append(neighbor)\n",
    "        return -1  # Should not reach here as there must be a leaf in the tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\"\"\"\n",
    "graph = {\n",
    "    1: [2, 3],\n",
    "    2: [1, 4, 5],\n",
    "    3: [1, 6, 7],\n",
    "    4: [2],\n",
    "    5: [2],\n",
    "    6: [3],\n",
    "    7: [3]\n",
    "}\n",
    "\n",
    "leaves = {4, 5, 6, 7}\n",
    "用visited去重，从1开始我们到2，然后到2后，我们可以到1，如果没有visited的话\n",
    "就会1->2, 2->1这样循环\n",
    "\n",
    "因为使用bfs, 一层一层的搜索，最早碰到的就是最近的\n",
    "\n",
    "构建graph, 如果是根节点，放入leaves。\n",
    "如果存在左节点，构建图，然后遍历左子树\n",
    "如果存在右节点，构建图，然后遍历右子树\n",
    "\n",
    "然后把目标值放入queue, 如果找到目标(leaves),就返回node\n",
    "遍历这个node的邻居，如果邻居还没访问过，就放入queue\n",
    "\"\"\"\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaves = []\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "                leaves.append(root.val)\n",
    "\n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "\n",
    "        build_graph(root)\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if node in leaves:\n",
    "                return node\n",
    "            \n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        \n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "        que = collections.deque(node for node in graph if node and node.val == k)\n",
    "        seen = set(que)\n",
    "        while que:\n",
    "\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                # 叶子结点\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                \n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        que.append(nei)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph=defaultdict(list)\n",
    "        def getGraph(root:Optional[TreeNode],parent:Optional[TreeNode]=None):\n",
    "            if root:\n",
    "                graph[root].append(parent)\n",
    "                graph[parent].append(root)\n",
    "                getGraph(root.left,root)\n",
    "                getGraph(root.right,root)\n",
    "        getGraph(root)\n",
    "        queue=deque(n for n in graph if n and n.val==k )\n",
    "        visited=set(queue)\n",
    "        while queue:\n",
    "            cur=queue.popleft()\n",
    "            if cur:\n",
    "                # 叶子结点，只有父节点可到达\n",
    "                if len(graph[cur])<=1:\n",
    "                    return cur.val\n",
    "                for adj in graph[cur]:\n",
    "                    if adj not in visited:\n",
    "                        visited.add(adj)\n",
    "                        queue.append(adj)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def findClosestLeaf(self, root, k):\n",
    "        graph = collections.defaultdict(list)\n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "\n",
    "        dfs(root)\n",
    "        queue = collections.deque(node for node in graph\n",
    "                                  if node and node.val == k)\n",
    "        seen = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        queue.append(nei)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if root.left == None and root.right == None:            #只有一个点，无法建图\n",
    "            if root.val == k:\n",
    "                return root.val\n",
    "            else:\n",
    "                return -1\n",
    "        head = 0\n",
    "        tail = 0\n",
    "        self.graph = defaultdict(list)\n",
    "        print(self.graph)\n",
    "        def dfs(node,parent):\n",
    "            if node:\n",
    "                if parent:\n",
    "                    self.graph[node].append(parent)\n",
    "                    self.graph[parent].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "        for node in self.graph:\n",
    "            if node.val == k:\n",
    "                start = node\n",
    "\n",
    "        queue = [start]\n",
    "        visited = [start]\n",
    "        while head<=tail:\n",
    "            jl = queue[head]\n",
    "            if not jl.left and not jl.right:\n",
    "                    return jl.val\n",
    "            for node in self.graph[jl]:\n",
    "\n",
    "                if node not in visited:\n",
    "                    visited.append(node)\n",
    "                    queue.append(node)\n",
    "                    tail+=1\n",
    "            head+=1        \n",
    "        \n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root.left and not root.right:\n",
    "            return root.val\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def dfs(node, parent = None):\n",
    "            if node:\n",
    "                graph[node].append(parent)\n",
    "                graph[parent].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        queue = deque(node for node in graph if node and node.val == k)\n",
    "        visited = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "            \n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in visited:\n",
    "                        visited.add(neighbor)\n",
    "                        queue.append(neighbor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findClosestLeaf(self, root, k):\n",
    "        graph = collections.defaultdict(list)\n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "\n",
    "        dfs(root)\n",
    "        queue = collections.deque(node for node in graph\n",
    "                                  if node and node.val == k)\n",
    "        seen = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        queue.append(nei)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        s=set()\n",
    "        def dfs(node, par):\n",
    "            if node:\n",
    "                graph[node.val].append(par)\n",
    "                graph[par.val].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "                if node.left==None and node.right==None:\n",
    "                    s.add(node.val)\n",
    "        dfs(root,root)\n",
    "        if k in s:\n",
    "            return k\n",
    "        q=deque()\n",
    "        vis=set()\n",
    "        vis.add(k)\n",
    "        for i in graph[k]:\n",
    "            if i.val in s:\n",
    "                return i.val\n",
    "            q.append(i)\n",
    "            vis.add(i.val)\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                temp=q.popleft()\n",
    "                for j in graph[temp.val]:\n",
    "                    if j.val in s:\n",
    "                        return j.val\n",
    "                    if j.val not in vis:\n",
    "                        q.append(j)\n",
    "                        vis.add(j.val)\n",
    "        return -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections  import defaultdict\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph=defaultdict(list)\n",
    "        def dfs(root:Optional[TreeNode],parent:Optional[TreeNode]):\n",
    "            if root:\n",
    "                graph[root].append(parent)\n",
    "                graph[parent].append(root)\n",
    "                dfs(root.left,root)\n",
    "                dfs(root.right,root)\n",
    "        dfs(root,None)\n",
    "        queue=deque(node for node in graph if node and node.val==k)\n",
    "        visited=set(queue)\n",
    "        while queue:\n",
    "            cur=queue.popleft()\n",
    "            if cur:\n",
    "                if len(graph[cur])<=1:\n",
    "                    return cur.val\n",
    "                for nei in graph[cur]:\n",
    "                    if nei not in visited:\n",
    "                        visited.add(nei)\n",
    "                        queue.append(nei)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        check=False\n",
    "        def dfs(node, par):\n",
    "            nonlocal check\n",
    "            if node:\n",
    "                graph[node.val].append(par)\n",
    "                graph[par.val].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "                if node.left==None and node.right==None and node.val==k:\n",
    "                    check=True\n",
    "        dfs(root,root)\n",
    "        if check:\n",
    "            return k\n",
    "        q=deque()\n",
    "        vis=set()\n",
    "        vis.add(k)\n",
    "        for i in graph[k]:\n",
    "            if not i.left and not i.right:\n",
    "                return i.val\n",
    "            q.append(i)\n",
    "            vis.add(i.val)\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                temp=q.popleft()\n",
    "                for j in graph[temp.val]:\n",
    "                    if not j.left and not j.right:\n",
    "                        return j.val\n",
    "                    if j.val not in vis:\n",
    "                        q.append(j)\n",
    "                        vis.add(j.val)\n",
    "        return -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        \n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "        que = collections.deque(node for node in graph if node and node.val == k)\n",
    "        seen = set(que)\n",
    "        while que:\n",
    "\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                \n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        que.append(nei)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        q = deque()\n",
    "        vis = set()\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val == k and not q:\n",
    "                    q.append(root)\n",
    "                    vis.add(root)\n",
    "                if root.left:\n",
    "                    g[root].append(root.left)\n",
    "                    g[root.left].append(root)\n",
    "                if root.right:\n",
    "                    g[root].append(root.right)\n",
    "                    g[root.right].append(root)\n",
    "                dfs(root.left)\n",
    "                dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        \n",
    "        while q:\n",
    "            root = q.popleft()\n",
    "            if not root.left and not root.right:\n",
    "                return root.val\n",
    "            for nx in g[root]:\n",
    "                if nx not in vis:\n",
    "                    vis.add(nx)\n",
    "                    q.append(nx)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        \n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "        que = collections.deque(node for node in graph if node and node.val == k)\n",
    "        seen = set(que)\n",
    "        while que:\n",
    "\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                # 叶子结点\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                \n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        que.append(nei)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
